/* ----------------------------------------------------------------------------
 * umm_malloc.c - a memory allocator for embedded systems (microcontrollers)
 *
 * See LICENSE for copyright notice
 * See README.md for acknowledgements and description of internals
 * ----------------------------------------------------------------------------
 *
 * R.Hempel 2007-09-22 - Original
 * R.Hempel 2008-12-11 - Added MIT License biolerplate
 *                     - realloc() now looks to see if previous block is free
 *                     - made common operations functions
 * R.Hempel 2009-03-02 - Added macros to disable tasking
 *                     - Added function to dump heap and check for valid free
 *                        pointer
 * R.Hempel 2009-03-09 - Changed name to umm_malloc to avoid conflicts with
 *                        the mm_malloc() library functions
 *                     - Added some test code to assimilate a free block
 *                        with the very block if possible. Complicated and
 *                        not worth the grief.
 * D.Frank 2014-04-02  - Fixed heap configuration when UMM_TEST_MAIN is NOT set,
 *                        added user-dependent configuration file umm_malloc_cfg.h
 * R.Hempel 2016-12-04 - Add support for Unity test framework
 *                     - Reorganize source files to avoid redundant content
 *                     - Move integrity and poison checking to separate file
 * R.Hempel 2017-12-29 - Fix bug in realloc when requesting a new block that
 *                        results in OOM error - see Issue 11
 * R.Hempel 2019-09-07 - Separate the malloc() and free() functionality into
 *                        wrappers that use critical section protection macros
 *                        and static core functions that assume they are
 *                        running in a protected con text. Thanks @devyte
 * R.Hempel 2020-01-07 - Add support for Fragmentation metric - See Issue 14，增加对碎片度量的支持
 * R.Hempel 2020-01-12 - Use explicitly sized values from stdint.h - See Issue 15
 * R.Hempel 2020-01-20 - Move metric functions back to umm_info - See Issue 29
 * R.Hempel 2020-02-01 - Macro functions are uppercased - See Issue 34
 * R.Hempel 2020-06-20 - Support alternate body size - See Issue 42
 * R.Hempel 2021-05-02 - Support explicit memory umm_init_heap() - See Issue 53
 * K.Whitlock 2023-07-06 - Add support for multiple heaps
 * ----------------------------------------------------------------------------
 */

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>

#include "umm_malloc_cfg.h"   // Override with umm_malloc_cfg_xxx.h
#include "umm_malloc.h"
#include "mlog.h"

#undef MLOG_LEVEL_CUR
#define MLOG_LEVEL_CUR MLOG_LEVEL_OFF

#define DBGLOG_TRACE(fmt, ...)        MLOG_DEBUG_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_DEBUG(fmt, ...)        MLOG_DEBUG_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_CRITICAL(fmt, ...)     MLOG_INFO_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_ERROR(fmt, ...)        MLOG_INFO_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_WARNING(fmt, ...)      MLOG_WARN_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_INFO(fmt, ...)         MLOG_ERROR_NO_ENDL(1, mDebugPrintf(fmt, ##__VA_ARGS__);)
#define DBGLOG_FORCE(force, fmt, ...) MLOG_FATAL_NO_ENDL(force, mDebugPrintf(fmt, ##__VA_ARGS__);)


/**
 * 外部定义的堆数组的首地址，和大小
 */
extern void *UMM_MALLOC_CFG_HEAP_ADDR;
extern uint32_t UMM_MALLOC_CFG_HEAP_SIZE;

/* ------------------------------------------------------------------------- */

/**
 * 链表索引值，非地址值，最大索引值为0x7FFF(32768)，[16:16]为0表示节点被使用
 * 为1表示节点空闲
 * 此处UMM_H_ATTPACKSUF并不会影响数据结构
 */
UMM_H_ATTPACKPRE typedef struct umm_ptr_t {
    uint16_t next;
    uint16_t prev;
} UMM_H_ATTPACKSUF umm_ptr;

/**
 * data前面被占用了4字节，因此data可以保证是4字节对齐的。
 * used: 所有节点链表，包括空闲的和正在使用的，两个相邻的空闲节点会被合并成1个
 * free: 当节点空闲时，该字段有效
 * used.next的[16:16]用于标记该节点是否被使用
 * 此处UMM_H_ATTPACKSUF并不会影响数据结构
 * 内存池被视为umm_block数组，数组的元素0和最后一个元素作为内存池的边界，不参与
 * 内存分配，链表的索引值即为数组索引值，用途连续的空间（通过一次申请或空闲）
 * 仅保留空间起点的数组元素，其他元素无效，起点的数组元素中used可用于寻找
 * 上/下一个有效节点（可以是被使用的或空闲的）。未使用的空间其free字段可用于
 * 索引上/下一个空闲节点
 */
UMM_H_ATTPACKPRE typedef struct umm_block_t {
    union {
        umm_ptr used;
    } header;
    union {
        umm_ptr free;
        uint8_t data[UMM_BLOCK_BODY_SIZE - sizeof(struct umm_ptr_t)];
    } body;
} UMM_H_ATTPACKSUF umm_block;

#define UMM_FREELIST_MASK ((uint16_t)(0x8000))
#define UMM_BLOCKNO_MASK  ((uint16_t)(0x7FFF))

/* ------------------------------------------------------------------------- */

#define UMM_HEAP       ((umm_block *)heap->pheap)
#define UMM_HEAPSIZE   (heap->heap_size)
#define UMM_NUMBLOCKS  (heap->numblocks)

#define UMM_BLOCKSIZE  (sizeof(umm_block))
#define UMM_BLOCK_LAST (UMM_NUMBLOCKS - 1)

/* -------------------------------------------------------------------------
 * These macros evaluate to the address of the block and data respectively
 */

#define UMM_BLOCK(b)  (UMM_HEAP[b])
#define UMM_DATA(b)   (UMM_BLOCK(b).body.data)

/* -------------------------------------------------------------------------
 * These macros evaluate to the index of the block - NOT the address!!!
 */

#define UMM_NBLOCK(b) (UMM_BLOCK(b).header.used.next)
#define UMM_PBLOCK(b) (UMM_BLOCK(b).header.used.prev)
#define UMM_NFREE(b)  (UMM_BLOCK(b).body.free.next)
#define UMM_PFREE(b)  (UMM_BLOCK(b).body.free.prev)

/* -------------------------------------------------------------------------
 * There are additional files that may be included here - normally it's
 * not a good idea to include .c files but in this case it keeps the
 * main umm_malloc file clear and prevents issues with exposing internal
 * data structures to other programs.
 * -------------------------------------------------------------------------
 */

#include "umm_integrity.c"
#include "umm_poison.c"
#include "umm_info.c"

/* ------------------------------------------------------------------------ */
/**
 * 内存池被设计成umm_block结构体数组，每个结构体有个双向链表的索引，还包含一
 * 部分可存放用户数据，在分配时在只需要第一个结构体的数据，后续的结构体可以
 * 全部用作用户数据，因而计算blocks时，需要分两种情况，1是一个结构体可存下
 * 2是还需要多个完整的结构体来存放。
 */
static uint16_t umm_blocks(size_t size) {

    /*
     * The calculation of the block size is not too difficult, but there are
     * a few little things that we need to be mindful of.
     *
     * When a block removed from the free list, the space used by the free
     * pointers is available for data. That's what the first calculation
     * of size is doing.
     *
     * We don't check for the special case of (size == 0) here as this needs
     * special handling in the caller depending on context. For example when we
     * realloc() a block to size 0 it should simply be freed.
     *
     * We do NOT need to check for allocating more blocks than the heap can
     * possibly hold - the allocator figures this out for us.
     *
     * There are only two cases left to consider:
     *
     * 1. (size <= body)  Obviously this is just one block
     * 2. (blocks > (2^15)) This should return ((2^15)) to force a
     *                      failure when the allocator runs
     *
     * If the requested size is greater that 32677-2 blocks (max block index
     * minus the overhead of the top and bottom bookkeeping blocks) then we
     * will return an incorrectly truncated value when the result is cast to
     * a uint16_t.
     */

    if (size <= (sizeof(((umm_block *)0)->body))) {
        return 1;
    }

    /*
     * If it's for more than that, then we need to figure out the number of
     * additional whole blocks the size of an umm_block are required, so
     * reduce the size request by the number of bytes in the body of the
     * first block.
     */

    size -= (sizeof(((umm_block *)0)->body));

    /* NOTE WELL that we take advantage of the fact that INT16_MAX is the
     * number of blocks that we can index in 15 bits :-)
     *
     * The below expression looks wierd, but it's right. Assuming body
     * size of 4 bytes and a block size of 8 bytes:
     *
     * BYTES (BYTES-BODY) (BYTES-BODY-1)/BLOCKSIZE BLOCKS
     *     1        n/a                        n/a      1
     *     5          1                          0      2
     *    12          8                          0      2
     *    13          9                          1      3
     */

    size_t blocks = (2 + ((size - 1) / (UMM_BLOCKSIZE)));

    if (blocks > (INT16_MAX)) {
        blocks = INT16_MAX;
    }

    return (uint16_t)blocks;
}

/* ------------------------------------------------------------------------ */
/*
 * Split the block `c` into two blocks: `c` and `c + blocks`.
 *
 * - `new_freemask` should be `0` if `c + blocks` used, or `UMM_FREELIST_MASK`
 *   otherwise.
 *
 * Note that free pointers are NOT modified by this function.
 * 将1个节点拆成两个节点
 * 起点  拆分点    结束
 * c     c+blocks  UMM_NBLOCK(c) & UMM_BLOCKNO_MASK
 */
static void umm_split_block(umm_heap *heap,
    uint16_t c,
    uint16_t blocks,
    uint16_t new_freemask) {

    UMM_NBLOCK(c + blocks) = (UMM_NBLOCK(c) & UMM_BLOCKNO_MASK) | new_freemask;
    UMM_PBLOCK(c + blocks) = c;

    UMM_PBLOCK(UMM_NBLOCK(c) & UMM_BLOCKNO_MASK) = (c + blocks);
    UMM_NBLOCK(c) = (c + blocks);
}

/* ------------------------------------------------------------------------ */

/**
 * 将一个节点从空闲链表上移除，也即将该节点的上一个节点和下一个节点直接相连,
 * 仅修改free链表
 */
static void umm_disconnect_from_free_list(umm_heap *heap, uint16_t c) {
    /* Disconnect this block from the FREE list */

    UMM_NFREE(UMM_PFREE(c)) = UMM_NFREE(c);
    UMM_PFREE(UMM_NFREE(c)) = UMM_PFREE(c);

    /* And clear the free block indicator */

    UMM_NBLOCK(c) &= (~UMM_FREELIST_MASK);
}

/* ------------------------------------------------------------------------
 * 向后同化，将下一个空闲的节点，合并到当前节点，当前节点可能是正在使用或
 * 空闲，在free()和realloc()中调用，由于
 * The umm_assimilate_up() function does not assume that UMM_NBLOCK(c)
 * has the UMM_FREELIST_MASK bit set. It only assimilates up if the
 * next block is free.
 */

static void umm_assimilate_up(umm_heap *heap, uint16_t c) {

    if (UMM_NBLOCK(UMM_NBLOCK(c)) & UMM_FREELIST_MASK) {

        /* 此处仅需要移除，在free()中会进行添加 */
        UMM_FRAGMENTATION_METRIC_REMOVE(UMM_NBLOCK(c));

        /*
         * The next block is a free block, so assimilate up and remove it from
         * the free list
         */

        DBGLOG_DEBUG("Assimilate up to next block, which is FREE\n");

        /* Disconnect the next block from the FREE list */

        /* 这里修改free链表，将下一个节点从free中移除 */
        umm_disconnect_from_free_list(heap, UMM_NBLOCK(c));

        /* Assimilate the next block with this one */

        /* 这里修改used链表，将下一个节点从used中移除 */
        UMM_PBLOCK(UMM_NBLOCK(UMM_NBLOCK(c)) & UMM_BLOCKNO_MASK) = c;
        UMM_NBLOCK(c) = UMM_NBLOCK(UMM_NBLOCK(c)) & UMM_BLOCKNO_MASK;
    }
}

/* ------------------------------------------------------------------------
 * 向前同化，即当前节点空闲了，如果上一节点空闲则合并两节点
 * freemask: 上一个节点是否空闲，在free()和在realloc()中上一个节点要被合入当
 * 前节点的类型会不同
 * The umm_assimilate_down() function assumes that UMM_NBLOCK(c) does NOT
 * have the UMM_FREELIST_MASK bit set. In other words, try to assimilate
 * up before assimilating down.
 */

static uint16_t umm_assimilate_down(umm_heap *heap, uint16_t c, uint16_t freemask) {

    // We are going to assimilate down to the previous block because
    // it was free, so remove it from the fragmentation metric

    /* 移除上一个节点的碎片统计 */
    UMM_FRAGMENTATION_METRIC_REMOVE(UMM_PBLOCK(c));

    /* 将当前节点从used中移除 */
    UMM_NBLOCK(UMM_PBLOCK(c)) = UMM_NBLOCK(c) | freemask;
    UMM_PBLOCK(UMM_NBLOCK(c)) = UMM_PBLOCK(c);

    if (freemask) {
        // We are going to free the entire assimilated block
        // so add it to the fragmentation metric. A good
        // compiler will optimize away the empty if statement
        // when UMM_INFO is not defined, so don't worry about
        // guarding it.

        /* 重新计算上一个节点的碎片信息 */
        UMM_FRAGMENTATION_METRIC_ADD(UMM_PBLOCK(c));
    }

    return UMM_PBLOCK(c);
}

/* ------------------------------------------------------------------------- */

void umm_multi_init_heap(umm_heap *heap, void *ptr, size_t size) {
    /* init heap pointer and size, and memset it to 0 */
#ifndef UMM_ALIGN
    /* 不需要对齐处理 */
    heap->pheap = ptr;
#else
    /* 新增，根据UMM_ALIGN进行4/8/16 ... 对齐处理 */
    uint32_t align = UMM_ALIGN - 1;
    uint32_t tmp1 = (uint32_t)ptr;
    uint32_t tmp2;
    tmp2 = (tmp1+align) & (~align);

    #if UMM_ALIGN >= 8
        /* 申请的内存会有1个umm_ptr头，故需要将堆的首地址前移或后移 */
        if ((tmp2-tmp1) >= sizeof(umm_ptr)) {
            tmp2 -= sizeof(umm_ptr);
        } else {
            tmp2 += UMM_ALIGN - sizeof(umm_ptr);
        }
    #endif

    /* 计算对齐后的堆地址和大小 */
    heap->pheap = (void *)tmp2;
    size -= tmp2 - tmp1;
    DBGLOG_DEBUG("Heap pool %08x(%d) align %08x(%d)\n", (uint32_t)ptr, 
                 size+tmp2-tmp1, tmp2, size);
#endif
    UMM_HEAPSIZE = size;
    /* 此处修改，最后一个数组元素仅使用used和free成员，不使用data成员，
       当UMM_BLOCK_BODY_SIZE=8时，free成员和data成员的大小是一样的也就不
       存在资源浪费 */
    UMM_NUMBLOCKS = ((UMM_HEAPSIZE-sizeof(umm_ptr)*2) / UMM_BLOCKSIZE) + 1;
    /* 此处修改，不进行堆清零操作 */
    memset(UMM_HEAP, 0x00, UMM_HEAPSIZE);

    /* setup initial blank heap structure */
    UMM_FRAGMENTATION_METRIC_INIT();

    /* Set up umm_block[0], which just points to umm_block[1] */
    /* 数组元素0固定为节点0，固定指向节点1 */
    UMM_NBLOCK(0) = 1;
    UMM_PBLOCK(0) = 0;
    UMM_NFREE(0) = 1;
    UMM_PFREE(0) = 1;

    /*
     * Now, we need to set the whole heap space as a huge free block. We should
     * not touch umm_block[0], since it's special: umm_block[0] is the head of
     * the free block list. It's a part of the heap invariant.
     *
     * See the detailed explanation at the beginning of the file.
     *
     * umm_block[1] has pointers:
     *
     * - next `umm_block`: the last one umm_block[n]
     * - prev `umm_block`: umm_block[0]
     *
     * Plus, it's a free `umm_block`, so we need to apply `UMM_FREELIST_MASK`
     *
     * And it's the last free block, so the next free block is 0 which marks
     * the end of the list. The previous block and free block pointer are 0
     * too, there is no need to initialize these values due to the init code
     * that memsets the entire umm_ space to 0.
     */
    /* 数组元素1固定为节点1，下一个节点是最后一个数组元素，标记当前节点是空闲
       的。上一个节点是节点0，对应为元素0。仅存在一个空闲节点，故free链表为0。
       由于取消了堆清零，此处补全了元素1的配置 */
    UMM_NBLOCK(1) = UMM_BLOCK_LAST | UMM_FREELIST_MASK;
    UMM_PBLOCK(1) = 0;
    UMM_NFREE(1) = 0;
    UMM_PFREE(1) = 0;

    /*
     * Last umm_block[n] has the next block index at 0, meaning it's
     * the end of the list, and the previous block is umm_block[1].
     *
     * The last block is a special block and can never be part of the
     * free list, so its pointers are left at 0 too.
     */
    /* 数组最后一个元素1固定为最后的节点，其下一个节点是0，表示空，上一个节点
       是节点1，即元素1，最后一个节点不参与空闲链表。由于取消了堆清零，此处补
       全了元素1的配置 */
    UMM_NBLOCK(UMM_BLOCK_LAST) = 0;
    UMM_PBLOCK(UMM_BLOCK_LAST) = 1;
    UMM_NFREE(UMM_BLOCK_LAST) = 0;
    UMM_PFREE(UMM_BLOCK_LAST) = 0;
}

void umm_multi_init(umm_heap *heap) {
    /* Initialize the heap from linker supplied values */

    umm_multi_init_heap(heap, UMM_MALLOC_CFG_HEAP_ADDR, UMM_MALLOC_CFG_HEAP_SIZE);
}

/* ------------------------------------------------------------------------
 * Must be called only from within critical sections guarded by
 * UMM_CRITICAL_ENTRY(id) and UMM_CRITICAL_EXIT(id).
 */

static void umm_free_core(umm_heap *heap, void *ptr) {

    uint16_t c;

    /*
     * FIXME: At some point it might be a good idea to add a check to make sure
     *        that the pointer we're being asked to free up is actually within
     *        the umm_heap!
     *
     * NOTE:  See the new umm_info() function that you can use to see if a ptr is
     *        on the free list!
     */

    /* Figure out which block we're in. Note the use of truncated division... */

    /* ptr在一个数组元素中都能够被正常释放 */
    c = (((uint8_t *)ptr) - (uint8_t *)(&(UMM_HEAP[0]))) / UMM_BLOCKSIZE;

    DBGLOG_DEBUG("Freeing block %6i\n", c);

    /* Now let's assimilate this block with the next one if possible. */

    umm_assimilate_up(heap, c);

    /* Then assimilate with the previous block if possible */

    if (UMM_NBLOCK(UMM_PBLOCK(c)) & UMM_FREELIST_MASK) {

        DBGLOG_DEBUG("Assimilate down to previous block, which is FREE\n");

        c = umm_assimilate_down(heap, c, UMM_FREELIST_MASK);
    } else {
        /*
         * The previous block is not a free block, so add this one to the head
         * of the free list
         */
        UMM_FRAGMENTATION_METRIC_ADD(c);

        DBGLOG_DEBUG("Just add to head of free list\n");

        /* 将空闲的块插到空闲链表的开头 */
        UMM_PFREE(UMM_NFREE(0)) = c;
        UMM_NFREE(c) = UMM_NFREE(0);
        UMM_PFREE(c)            = 0;
        UMM_NFREE(0) = c;

        UMM_NBLOCK(c) |= UMM_FREELIST_MASK;
    }
}

/* ------------------------------------------------------------------------ */

void umm_multi_free(umm_heap *heap, void *ptr) {
    UMM_CRITICAL_DECL(id_free);

    UMM_CHECK_INITIALIZED();

    /* If we're being asked to free a NULL pointer, well that's just silly! */

    if ((void *)0 == ptr) {
        DBGLOG_DEBUG("free a null pointer -> do nothing\n");

        return;
    }

    /* If we're being asked to free an out of range pointer - do nothing */
    /* TODO: remove the check for NULL pointer later */

    if ((ptr < heap->pheap) || ((size_t)ptr >= (size_t)heap->pheap + heap->heap_size)) {
        DBGLOG_DEBUG("free an out of range pointer -> do nothing\n");

        return;
    }

    /* Free the memory withing a protected critical section */

    UMM_CRITICAL_ENTRY(id_free);

    umm_free_core(heap, ptr);

    UMM_CRITICAL_EXIT(id_free);
}

/* ------------------------------------------------------------------------
 * Must be called only from within critical sections guarded by
 * UMM_CRITICAL_ENTRY(id) and UMM_CRITICAL_EXIT(id).
 */

static void *umm_malloc_core(umm_heap *heap, size_t size) {
    uint16_t blocks;
    uint16_t blockSize = 0;

    uint16_t bestSize;
    uint16_t bestBlock;

    uint16_t cf;

    /* 计算需要多少个数组元素 */
    blocks = umm_blocks(size);

    /*
     * Now we can scan through the free list until we find a space that's big
     * enough to hold the number of blocks we need.
     *
     * This part may be customized to be a best-fit, worst-fit, or first-fit
     * algorithm
     */

    /* 节点0，固定为元素0，执行第一个空闲的链表 */
    cf = UMM_NFREE(0);

    bestBlock = UMM_NFREE(0);
    bestSize = 0x7FFF;

    while (cf) {
        blockSize = (UMM_NBLOCK(cf) & UMM_BLOCKNO_MASK) - cf;

        DBGLOG_TRACE("Looking at block %6i size %6i\n", cf, blockSize);

        #if defined UMM_BEST_FIT
        /* 便利全部空间，找一个最小且满足目标需求的块 */
        if ((blockSize >= blocks) && (blockSize < bestSize)) {
            bestBlock = cf;
            bestSize = blockSize;
        }
        #elif defined UMM_FIRST_FIT
        /* This is the first block that fits! */
        /* 找到了就立即返回 */
        if ((blockSize >= blocks)) {
            break;
        }
        #else
        #error "No UMM_*_FIT is defined - check umm_malloc_cfg.h"
        #endif

        cf = UMM_NFREE(cf);
    }

    /* 如果定义了UMM_FIRST_FIT，则会被编译器优化掉 */
    if (0x7FFF != bestSize) {
        cf = bestBlock;
        blockSize = bestSize;
    }

    if (UMM_NBLOCK(cf) & UMM_BLOCKNO_MASK && blockSize >= blocks) {

        UMM_FRAGMENTATION_METRIC_REMOVE(cf);

        /*
         * This is an existing block in the memory heap, we just need to split off
         * what we need, unlink it from the free list and mark it as in use, and
         * link the rest of the block back into the freelist as if it was a new
         * block on the free list...
         */

        if (blockSize == blocks) {
            /* It's an exact fit and we don't neet to split off a block. */
            DBGLOG_DEBUG("Allocating %6i blocks starting at %6i - exact\n", blocks, cf);

            /* Disconnect this block from the FREE list */

            umm_disconnect_from_free_list(heap, cf);
        } else {

            /* It's not an exact fit and we need to split off a block. */
            DBGLOG_DEBUG("Allocating %6i blocks starting at %6i - existing\n", blocks, cf);

            /*
             * split current free block `cf` into two blocks. The first one will be
             * returned to user, so it's not free, and the second one will be free.
             */
            umm_split_block(heap, cf, blocks, UMM_FREELIST_MASK /*new block is free*/);

            /* 拆分后当前节点的下一个节点是空闲的，进行碎片信息统计 */
            UMM_FRAGMENTATION_METRIC_ADD(UMM_NBLOCK(cf));

            /*
             * `umm_split_block()` does not update the free pointers (it affects
             * only free flags), but effectively we've just moved beginning of the
             * free block from `cf` to `cf + blocks`. So we have to adjust pointers
             * to and from adjacent free blocks.
             */

            /* previous free block */
            UMM_NFREE(UMM_PFREE(cf)) = cf + blocks;
            UMM_PFREE(cf + blocks) = UMM_PFREE(cf);

            /* next free block */
            UMM_PFREE(UMM_NFREE(cf)) = cf + blocks;
            UMM_NFREE(cf + blocks) = UMM_NFREE(cf);
        }

    } else {
        /* Out of memory */

        DBGLOG_DEBUG("Can't allocate %5i blocks\n", blocks);

        return (void *)NULL;
    }

    return (void *)&UMM_DATA(cf);
}

/* ------------------------------------------------------------------------ */

void *umm_multi_malloc(umm_heap *heap, size_t size) {
    UMM_CRITICAL_DECL(id_malloc);

    void *ptr = NULL;

    UMM_CHECK_INITIALIZED();

    /*
     * the very first thing we do is figure out if we're being asked to allocate
     * a size of 0 - and if we are we'll simply return a null pointer. if not
     * then reduce the size by 1 byte so that the subsequent calculations on
     * the number of blocks to allocate are easier...
     * 申请0字节的空间，返回空
     */

    if (0 == size) {
        DBGLOG_DEBUG("malloc a block of 0 bytes -> do nothing\n");

        return ptr;
    }

    /* Allocate the memory withing a protected critical section */

    UMM_CRITICAL_ENTRY(id_malloc);

    ptr = umm_malloc_core(heap, size);

    UMM_CRITICAL_EXIT(id_malloc);

    return ptr;
}

/* ------------------------------------------------------------------------ */

void *umm_multi_realloc(umm_heap *heap, void *ptr, size_t size) {
    UMM_CRITICAL_DECL(id_realloc);

    uint16_t blocks;
    uint16_t blockSize;
    uint16_t prevBlockSize = 0;
    uint16_t nextBlockSize = 0;

    uint16_t c;

    size_t curSize;

    UMM_CHECK_INITIALIZED();

    /*
     * This code looks after the case of a NULL value for ptr. The ANSI C
     * standard says that if ptr is NULL and size is non-zero, then we've
     * got to work the same a malloc(). If size is also 0, then our version
     * of malloc() returns a NULL pointer, which is OK as far as the ANSI C
     * standard is concerned.
     * ptr为0时，等于malloc()
     */

    if (((void *)NULL == ptr)) {
        DBGLOG_DEBUG("realloc the NULL pointer - call malloc()\n");

        return umm_multi_malloc(heap, size);
    }

    /*
     * Now we're sure that we have a non_NULL ptr, but we're not sure what
     * we should do with it. If the size is 0, then the ANSI C standard says that
     * we should operate the same as free.
     * size为0时，等于free()
     */

    if (0 == size) {
        DBGLOG_DEBUG("realloc to 0 size, just free the block\n");

        umm_multi_free(heap, ptr);

        return (void *)NULL;
    }

    /*
     * Otherwise we need to actually do a reallocation. A naiive approach
     * would be to malloc() a new block of the correct size, copy the old data
     * to the new block, and then free the old block.
     *
     * While this will work, we end up doing a lot of possibly unnecessary
     * copying. So first, let's figure out how many blocks we'll need.
     */

    blocks = umm_blocks(size);

    /* Figure out which block we're in. Note the use of truncated division... */

    c = (((uint8_t *)ptr) - (uint8_t *)(&(UMM_HEAP[0]))) / UMM_BLOCKSIZE;

    /* Figure out how big this block is ... the free bit is not set :-) */

    blockSize = (UMM_NBLOCK(c) - c);

    /* Figure out how many bytes are in this block */

    curSize = (blockSize * UMM_BLOCKSIZE) - (sizeof(((umm_block *)0)->header));

    /* Protect the critical section... */
    UMM_CRITICAL_ENTRY(id_realloc);

    /* Now figure out if the previous and/or next blocks are free as well as
     * their sizes - this will help us to minimize special code later when we
     * decide if it's possible to use the adjacent blocks.
     *
     * We set prevBlockSize and nextBlockSize to non-zero values ONLY if they
     * are free!
     */

    if ((UMM_NBLOCK(UMM_NBLOCK(c)) & UMM_FREELIST_MASK)) {
        nextBlockSize = (UMM_NBLOCK(UMM_NBLOCK(c)) & UMM_BLOCKNO_MASK) - UMM_NBLOCK(c);
    }

    if ((UMM_NBLOCK(UMM_PBLOCK(c)) & UMM_FREELIST_MASK)) {
        prevBlockSize = (c - UMM_PBLOCK(c));
    }

    DBGLOG_DEBUG("realloc blocks %i blockSize %i nextBlockSize %i prevBlockSize %i\n", blocks, blockSize, nextBlockSize, prevBlockSize);

    /*
     * Ok, now that we're here we know how many blocks we want and the current
     * blockSize. The prevBlockSize and nextBlockSize are set and we can figure
     * out the best strategy for the new allocation as follows:
     *
     * 1. If the new block is the same size or smaller than the current block do
     *    nothing.
     * 2. If the next block is free and adding it to the current block gives us
     *    EXACTLY enough memory, assimilate the next block. This avoids unwanted
     *    fragmentation of free memory.
     *
     * The following cases may be better handled with memory copies to reduce
     * fragmentation
     *
     * 3. If the previous block is NOT free and the next block is free and
     *    adding it to the current block gives us enough memory, assimilate
     *    the next block. This may introduce a bit of fragmentation.
     * 4. If the prev block is free and adding it to the current block gives us
     *    enough memory, remove the previous block from the free list, assimilate
     *    it, copy to the new block.
     * 5. If the prev and next blocks are free and adding them to the current
     *    block gives us enough memory, assimilate the next block, remove the
     *    previous block from the free list, assimilate it, copy to the new block.
     * 6. Otherwise try to allocate an entirely new block of memory. If the
     *    allocation works free the old block and return the new pointer. If
     *    the allocation fails, return NULL and leave the old block intact.
     *
     * TODO: Add some conditional code to optimise for less fragmentation
     *       by simply allocating new memory if we need to copy anyways.
     *
     * All that's left to do is decide if the fit was exact or not. If the fit
     * was not exact, then split the memory block so that we use only the requested
     * number of blocks and add what's left to the free list.
     */

    //  Case 1 - block is same size or smaller，申请的比原来的小
    if (blockSize >= blocks) {
        DBGLOG_DEBUG("realloc the same or smaller size block - %i, do nothing\n", blocks);
        /* This space intentionally left blank，此处释放的动作稍后进行 */

        //  Case 2 - block + next block fits EXACTLY，当前节点加下一个节点，刚刚好
    } else if ((blockSize + nextBlockSize) == blocks) {
        DBGLOG_DEBUG("exact realloc using next block - %i\n", blocks);
        umm_assimilate_up(heap, c);
        blockSize += nextBlockSize;

        //  Case 3 - prev block NOT free and block + next block fits，
        //           前一个节点不空闲，仅考虑下一个节点
    } else if (0 == prevBlockSize) {
        /* 下一个节点富足，则合并下一个节点 */
        if ((blockSize + nextBlockSize) >= blocks) {
            DBGLOG_DEBUG("realloc using next block - %i\n", blocks);
            umm_assimilate_up(heap, c);
            blockSize += nextBlockSize;
        } else {
            /* 下一个节点不富足，则只能重新申请 */
            goto CASE6;
        }

        //  Case 4 - prev block + block fits，前一个节点加当前节点足够，向前
        //           合并是为了减少内存碎片
    } else if ((prevBlockSize + blockSize) >= blocks) {
        DBGLOG_DEBUG("realloc using prev block - %i\n", blocks);
        umm_disconnect_from_free_list(heap, UMM_PBLOCK(c));
        c = umm_assimilate_down(heap, c, 0);
        memmove((void *)&UMM_DATA(c), ptr, curSize);
        ptr = (void *)&UMM_DATA(c);
        blockSize += prevBlockSize;

        //  Case 5 - prev block + block + next block fits
    } else if ((prevBlockSize + blockSize + nextBlockSize) >= blocks) {
        DBGLOG_DEBUG("realloc using prev and next block - %i\n", blocks);
        umm_assimilate_up(heap, c);
        umm_disconnect_from_free_list(heap, UMM_PBLOCK(c));
        c = umm_assimilate_down(heap, c, 0);
        memmove((void *)&UMM_DATA(c), ptr, curSize);
        ptr = (void *)&UMM_DATA(c);
        blockSize += (prevBlockSize + nextBlockSize);

        //  Case 6 - default is we need to realloc a new block
    } else {
CASE6:
        DBGLOG_DEBUG("realloc a completely new block %i\n", blocks);
        void *oldptr = ptr;
        if ((ptr = umm_malloc_core(heap, size))) {
            DBGLOG_DEBUG("realloc %i to a bigger block %i, copy, and free the old\n", blockSize, blocks);
            memcpy(ptr, oldptr, curSize);
            umm_free_core(heap, oldptr);
        } else {
            DBGLOG_DEBUG("realloc %i to a bigger block %i failed - return NULL and leave the old block!\n", blockSize, blocks);
            /* This space intentionally left blnk */
        }
        blockSize = blocks;
    }

    /* Now all we need to do is figure out if the block fit exactly or if we
     * need to split and free ...
     */

    if (blockSize > blocks) {
        DBGLOG_DEBUG("split and free %i blocks from %i\n", blocks, blockSize);
        umm_split_block(heap,c, blocks, 0);
        umm_free_core(heap, (void *)&UMM_DATA(c + blocks));
    }

    /* Release the critical section... */
    UMM_CRITICAL_EXIT(id_realloc);

    return ptr;
}

/* ------------------------------------------------------------------------ */

void *umm_multi_calloc(umm_heap *heap, size_t num, size_t item_size) {
    void *ret;

    ret = umm_multi_malloc(heap, (size_t)(item_size * num));

    if (ret) {
        memset(ret, 0x00, (size_t)(item_size * num));
    }

    return ret;
}

/* ------------------------------------------------------------------------ */

/* Single-heap functions */

struct umm_heap_config umm_heap_current; // The global heap for single-heap use

/**
 * 通过配置UMM_ALIGN可以确保分配出来的内存是4/8/16 ... 对齐的
 */
void umm_init_heap(void *ptr, size_t size){
    umm_multi_init_heap(&umm_heap_current, ptr, size);
}

void umm_init(void){
    umm_multi_init(&umm_heap_current);
}

void *umm_malloc(size_t size){
    return umm_multi_malloc(&umm_heap_current, size);
}

void *umm_calloc(size_t num, size_t size){
    return umm_multi_calloc(&umm_heap_current, num, size);
}

/**
 * ptr为0时，等于malloc(), size为0时，等于free()
 */
void *umm_realloc(void *ptr, size_t size){
    return umm_multi_realloc(&umm_heap_current, ptr, size);
}

void umm_free(void *ptr){
    umm_multi_free(&umm_heap_current, ptr);
}
